package com.cty._03_SolutionSeekingMindset._32_03_PrintTreeInZigzag;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * @Auther: cty
 * @Date: 2020/7/11 15:58
 * @Description: 面试题32（三）：之字形打印二叉树
 * 题目：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺
 * 序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，
 * 其他行以此类推。
 * @version: 1.0
 */
public class PrintTreeInZigzag {

    public static void printTree(BinaryTreeNode treeRoot){
        if(treeRoot == null)
            return;

        Stack<BinaryTreeNode>[] levels = new Stack[2];
        levels[0] = new Stack<>();
        levels[1] = new Stack<>();
        levels[0].push(treeRoot);
        int current = 0;
        int next = 1;

        while(!levels[0].isEmpty() || !levels[1].isEmpty()){

            BinaryTreeNode temp = levels[current].pop();
            System.out.print(temp.value + " ");

            if(current == 0){
                if(temp.leftChild != null)
                    levels[next].push(temp.leftChild);
                if(temp.rightChild != null)
                    levels[next].push(temp.rightChild);
            }else{
                if(temp.rightChild != null)
                    levels[next].push(temp.rightChild);
                if(temp.leftChild != null)
                    levels[next].push(temp.leftChild);
            }  // end else

            if(levels[current].isEmpty()){
                System.out.println();
                current = 1 - current;
                next = 1 - next;
            }  // end if
        }  // end while()
    }  // end printTree()

}  // end class

class BinaryTreeNode{
    int value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){}

    public BinaryTreeNode(int value){this.value = value;}
}  // end BinaryTreeNode
